package com.LeeCode;

/**
 * 分割正方形 I
 */

public class Code3453 {
    public static void main(String[] args) {

    }

    public double separateSquares(int[][] squares) {
        long totArea = 0;
        int maxY = 0;
        for (int[] sq : squares) {
            int l = sq[2];
            totArea += (long) l * l;
            maxY = Math.max(maxY, sq[1] + l);
        }

        double left = 0;
        double right = maxY;
        for (int i = 0; i < 47; i++) {
            double mid = (left + right) / 2;
            if (check(squares, mid, totArea)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return (left + right) / 2; // 区间中点误差小
    }

    private boolean check(int[][] squares, double y, long totArea) {
        double area = 0;
        for (int[] sq : squares) {
            double yi = sq[1];
            if (yi < y) {
                double l = sq[2];
                area += l * Math.min(y - yi, l);
            }
        }
        return area >= totArea / 2.0;
    }
}
